home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _p_aux_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  10.1 KB  |  450 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _p_aux_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/p_aux_heap.h>
  17.  
  18. static p_aux_heap const *class_ptr;
  19.  
  20. #define comparison_link(with_el,new_el)\
  21.   if ((cmp(with_el->key,new_el->key)<0)||(with_el==minptr))\
  22.    {  with_el->r_child=new_el->r_child;\
  23.       if (with_el->r_child!=nil)\
  24.               with_el->r_child->parent=with_el;\
  25.       new_el->r_child=with_el->l_child;\
  26.       if (new_el->r_child!=nil)\
  27.               new_el->r_child->parent=new_el;\
  28.       new_el->parent=with_el;  \
  29.       with_el->l_child=new_el; }\
  30.   else\
  31.     { with_el->r_child=new_el->l_child;\
  32.       if (with_el->r_child!=nil)\
  33.               with_el->r_child->parent=with_el;\
  34.       new_el->parent=with_el->parent;\
  35.       if (new_el->parent!=nil)\
  36.               new_el->parent->r_child=new_el; \
  37.       new_el->l_child=with_el;\
  38.       with_el->parent=new_el;\
  39.       with_el = new_el; }
  40.  
  41. #define int_comparison_link(with_el,new_el)\
  42.   if ((with_el->key < new_el->key)||(with_el==minptr))\
  43.     { with_el->r_child=new_el->r_child;\
  44.       if (with_el->r_child!=nil)\
  45.               with_el->r_child->parent=with_el;\
  46.       new_el->r_child=with_el->l_child;\
  47.       if (new_el->r_child!=nil)\
  48.               new_el->r_child->parent=new_el;\
  49.       new_el->parent=with_el;  \
  50.       with_el->l_child=new_el; }\
  51.   else\
  52.     { with_el->r_child=new_el->l_child;\
  53.       if (with_el->r_child!=nil)\
  54.               with_el->r_child->parent=with_el;\
  55.       new_el->parent=with_el->parent;\
  56.       if (new_el->parent!=nil)\
  57.               new_el->parent->r_child=new_el; \
  58.       new_el->l_child=with_el;\
  59.       with_el->parent=new_el;\
  60.       with_el = new_el; }
  61.  
  62.  
  63. //&&&&&&&&&&&&&&&&  p_heap &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  64.  
  65. //======= construct ===================================================
  66.  
  67. p_aux_heap::p_aux_heap()
  68. {
  69.     item_count=0;
  70. }
  71.     
  72. //====== construct (p_aux_heap&) ===========================================
  73.  
  74. p_aux_heap::p_aux_heap(const p_aux_heap& with)
  75. {
  76.     
  77.     item_count =0;
  78.     if((this!=&with)&&(with.item_count>0)){
  79.     class_ptr=&with;
  80.     head=new ph_item(with.head->key,with.head->inf);
  81.     class_ptr->copy_key(head->key);
  82.     class_ptr->copy_inf(head->inf);
  83.     item_count++;
  84.     if (with.head->l_child!=nil)
  85.           do_copy(head,with.head->l_child,true);
  86.     if (with.head->r_child!=nil)
  87.         do_copy(head,with.head->r_child,false);
  88.     class_ptr=this;
  89.     }
  90. }
  91.  
  92. //====== operator = =====================================================
  93.  
  94. p_aux_heap& p_aux_heap::operator=(const p_aux_heap& with)
  95. {
  96.       if(this!=&with){
  97.      if((with.item_count>0)&&(item_count>0))
  98.         clear();
  99.     class_ptr=&with;
  100.     head=new ph_item(with.head->key,with.head->inf);
  101.     class_ptr->copy_key(head->key);
  102.     class_ptr->copy_inf(head->inf);
  103.     item_count++;
  104.     if (with.head->l_child!=nil)
  105.           do_copy(head,with.head->l_child,true);
  106.     if (with.head->r_child!=nil)
  107.         do_copy(head,with.head->r_child,false);
  108.     class_ptr=this;
  109.         
  110.     }
  111.     return(*this);
  112. }
  113.  
  114.  
  115.  
  116. //====== do_copy ======================================================
  117.  
  118. void p_aux_heap::do_copy(ph_item* father,ph_item* from,bool direction)
  119. {
  120. // direction : false=right true=left
  121.  
  122.     
  123.     ph_item* hilf=new ph_item(from->key,from->inf);
  124.     class_ptr->copy_key(hilf->key);
  125.     class_ptr->copy_inf(hilf->inf);
  126.     if (class_ptr->minptr==from)
  127.         minptr=hilf;
  128.     item_count++;
  129.  
  130.     hilf->parent=father;
  131.     if (direction)
  132.         father->l_child=hilf;
  133.     else
  134.         father->r_child=hilf;
  135.  
  136.     if (from->l_child!=nil)
  137.         do_copy(hilf,from->l_child,true);
  138.         
  139.     if (from->r_child!=nil)
  140.         do_copy(hilf,from->r_child,false);
  141. }
  142.         
  143.  
  144.  
  145.  
  146.  
  147. //======= insert =======================================================
  148.  
  149. ph_item* p_aux_heap::insert(GenPtr key,GenPtr inf)
  150. {    
  151.     ph_item* help;
  152.  
  153.     
  154.     help = new ph_item(key,inf);
  155.     copy_key(help->key);
  156.     copy_inf(help->inf);
  157.  
  158.     if (item_count==0)    // very first element
  159.     {
  160.             
  161.         item_count++;
  162.         head=help;
  163.         minptr=help;
  164.         return head;
  165.     }
  166.         
  167.     else{                // just another element
  168.         
  169.         item_count++;
  170.         if(cmp(minptr->key,help->key)>=0)
  171.             minptr=help;
  172.  
  173.         if (head->r_child==nil)
  174.         {
  175.             help->parent=head;
  176.             head->r_child=help;
  177.         }
  178.         else
  179.         {
  180.             help->r_child=head->r_child;
  181.             head->r_child->parent=help;    
  182.             head->r_child=help;
  183.             help->parent=head;
  184.         }    // insert at the beginning of the r_child of head
  185.  
  186.         return help;
  187.     }
  188.  
  189.     
  190. }
  191.  
  192.  
  193. // ====== decrease_key ==================================================
  194.  
  195. void p_aux_heap::decrease_key(ph_item* which,GenPtr key)
  196. {
  197.     
  198.  
  199.   if (cmp(key,which->key)<=0)   // smaler or equal compared to the old key
  200.   {
  201.     clear_key(which->key);    
  202.     which->key=key;
  203.     copy_key(which->key);
  204.     if (cmp(which->key,minptr->key)<=0)
  205.         minptr=which;
  206.     if (which!=head)    // which is not already minimum
  207.     {  
  208.         if (which->parent->l_child==which){
  209.             if (which->r_child!=nil){
  210.                 which->parent->l_child=which->r_child;
  211.                 which->r_child->parent=which->parent;
  212.                 which->r_child=nil;
  213.             }
  214.             else
  215.                 which->parent->l_child=nil;
  216.         }
  217.         else {
  218.             if (which->r_child!=nil){
  219.                 which->parent->r_child=which->r_child;
  220.                 which->r_child->parent=which->parent;
  221.                 which->r_child=nil;
  222.             }
  223.             else
  224.                 which->parent->r_child=nil;
  225.         }
  226.  
  227.                 
  228.         if (head->r_child==nil){
  229.             head->r_child=which;
  230.             which->parent=head;
  231.         }
  232.         else
  233.         {
  234.             which->r_child=head->r_child;
  235.             head->r_child->parent=which;
  236.             head->r_child=which;
  237.             which->parent=head;
  238.                 
  239.         }        
  240.     }
  241.     
  242.   }
  243. }
  244.  
  245.                 
  246.         
  247. //========= delete_min_aux_multipass ()  (auxiliary multipass algorithm) =============
  248.  
  249. void p_aux_heap::delete_min_multipass()
  250. {  
  251.    ph_item *help;    
  252.  
  253.    if (head->r_child!=nil){
  254.     if (head->r_child->r_child!=nil){
  255.         help=head->r_child;
  256.         help->parent=nil;
  257.         help=multipass(help);
  258.     }
  259.           comparison_link(head,help);    // vorher head = ...
  260.     if (head->parent==help)
  261.         head=help;
  262.    }
  263.     
  264.  
  265.    if (item_count==1)    // only one element in structure
  266.    {
  267.     clear_key(head->key);
  268.     clear_inf(head->inf);
  269.     delete head;
  270.     item_count=0;
  271.    }
  272.    else
  273.    {
  274.          head=head->l_child;
  275.     clear_key(head->parent->key);
  276.     clear_inf(head->parent->inf);
  277.     delete head->parent;    // delete min
  278.     head->parent=nil;
  279.     item_count--;
  280.  
  281.      
  282.       if (head->r_child!=nil)    // there are two ore more consecutive elements
  283.           head=multipass(head);
  284.  
  285.   }// end else
  286.  
  287. minptr=head;
  288.  
  289.  
  290. }
  291.  
  292. //======== delete_min_aux_twopass, (auxiliary twopass algorithm) =============
  293.  
  294. void p_aux_heap::delete_min_twopass()
  295. {
  296.   ph_item *help;    
  297.  
  298.    if (head->r_child!=nil){
  299.     help=head->r_child;
  300.     if (head->r_child->r_child!=nil){
  301.         help->parent=nil;
  302.         help=multipass(help);
  303.     }
  304.        comparison_link(head,help);
  305.    }
  306.  
  307.      
  308.   
  309.    if (item_count==1)    // only one element in structure
  310.    {
  311.     clear_key(head->key);
  312.     clear_inf(head->inf);
  313.     delete head;
  314.     item_count=0;
  315.    }
  316.    else
  317.    {
  318.          head=head->l_child;
  319.     clear_key(head->parent->key);
  320.     clear_inf(head->parent->inf);
  321.     delete head->parent;    // delete min
  322.     head->parent=nil;
  323.     item_count--;
  324.     
  325.       if (head->r_child!=nil)    // there are two ore more consecutive elements
  326.           head=twopass(head);
  327.  
  328.    } // end else
  329.  
  330. minptr=head;
  331.  
  332. }
  333.         
  334. // ============== twopass ================================================              
  335.         
  336. ph_item*  p_aux_heap::twopass(ph_item* head)
  337. {
  338.  //pass 1 : left to right comparison link (successive pairs of root nodes)
  339.  
  340.   register ph_item* help1,*help2;
  341.  
  342.   help1=head;
  343.   help2=head->r_child;
  344.   
  345.   if (int_type())
  346.         while (help2!=nil)               // there are 2 ore more elements left
  347.         { head=help1->r_child->r_child;   // use of head as a helper
  348.           int_comparison_link(help1,help2);
  349.                 
  350.           if (head!=nil)       // first case comp _link
  351.              if (head->r_child!=nil)
  352.                { // second case
  353.                  // now we have to more nodes to test
  354.                  help2=head->r_child;
  355.                  help1=head;
  356.                 }
  357.              else
  358.                help2=nil;
  359.            else
  360.              { head=help1;     // last element in list
  361.                help2=nil;
  362.               }
  363.           }
  364.    else
  365.         while (help2!=nil)
  366.         { head=help1->r_child->r_child;
  367.           comparison_link(help1,help2);
  368.                 
  369.           if (head!=nil)
  370.              if (head->r_child!=nil)
  371.                { help2=head->r_child;
  372.                  help1=head;
  373.                 }
  374.              else
  375.                help2=nil;
  376.            else
  377.              { head=help1;
  378.                help2=nil;
  379.               }
  380.          }
  381.  
  382.   //pass 2 : right to left comparison link (allways the two rightmost nodes)
  383.  
  384.         help1=head->parent;
  385.         help2=head;
  386.  
  387.    if (int_type())
  388.         while (help1!=nil)
  389.         { int_comparison_link(help1,help2);
  390.       head=help1;
  391.           help2=help1;
  392.           help1=help1->parent;
  393.          }
  394.     else
  395.         while (help1!=nil)
  396.         { comparison_link(help1,help2);
  397.       head=help1;
  398.           help2=help1;
  399.           help1=help1->parent; 
  400.      }
  401.         
  402.  // head points now again to the very first element
  403.  
  404.  return(head);
  405.  
  406. }
  407.  
  408. // ================ multipass ==========================================
  409.  
  410. ph_item* p_aux_heap::multipass(ph_item* head)
  411. {
  412.           // now pass 1 (multi times) : left to right comparison link (successive pairs of root nodes)
  413.        ph_item* save=head;      
  414.        ph_item* help1,*help2;
  415.  
  416.        while(head->r_child!=nil)
  417.        { save=head;
  418.          help1=head;
  419.          help2=head->r_child;
  420.         
  421.          while (help2!=nil)      // there are 2 ore more elements left
  422.          { save=help1->r_child->r_child; // use of save as a helper
  423.            comparison_link(help1,help2);
  424.        if (help1->parent==help2)
  425.         help1=help2;
  426.                 
  427.            if (save!=nil)       // first case comp _link
  428.              if (save->r_child!=nil)
  429.                 { // second case
  430.                   // now we have to more nodes to test
  431.                   help2=save->r_child;
  432.                   help1=save;
  433.                  }
  434.               else
  435.                  help2=nil;
  436.            else
  437.               { save=help1;     // last element in list
  438.                 help2=nil;
  439.                }
  440.          } // end while (help2!=nil)
  441.  
  442.  
  443.            if (head->parent!=nil)      // may be first element is child (comp link)
  444.              head=head->parent;
  445.  
  446.     } // end while (repeat pass 1)
  447.  
  448.   return(head);
  449. }
  450.